package main

// 438. 找到字符串中所有字母异位词
func main() {
	//s := "cbaebabacd"
	s := "abab"
	//p := "abc"
	p := "ab"

	anagrams := findAnagrams(s, p)
	for _, i := range anagrams {
		println(i)
	}
}

func findAnagrams(s string, p string) []int {
	var res []int

	if len(s) < len(p) {
		return res
	}

	sArray, pArray := [26]int{}, [26]int{}
	for idx, char := range p {
		pArray[char-'a']++
		sArray[s[idx]-'a']++
	}

	if sArray == pArray {
		res = append(res, 0)
	}

	pLen := len(p)
	sLen := len(s)
	for i := 0; i < sLen-pLen; i++ {
		sArray[s[i]-'a']--
		sArray[s[i+pLen]-'a']++

		if sArray == pArray {
			res = append(res, i+1)
		}
	}

	return res
}

// 给定两个字符串 s 和 p，找到 s 中所有 p 的
//异位词
// 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
//
//
//
//示例 1:
//
//输入: s = "cbaebabacd", p = "abc"
//输出: [0,6]
//解释:
//起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
//起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
// 示例 2:
//
//输入: s = "abab", p = "ab"
//输出: [0,1,2]
//解释:
//起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
//起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
//起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
//
//
//提示:
//
//1 <= s.length, p.length <= 3 * 104
//s 和 p 仅包含小写字母
